As an example, systems and methods for generating 2-dimensional (2-D) or 3-dimensional (3-D) representations of an environment can be useful in a variety of applications, such as in automated navigation systems and methods. For example, such automated systems and methods could be used to help guide a vehicle through the environment. As used herein, a vehicle can be any platform capable of translation through the environment, which may or may not be configured for carrying human passengers.
Previous attempts at providing automated navigation have been limited in their flexibility, and also in their success. Most current commercial systems employ a “guide-path following” technique. In this type of system, a guide-path is fixed to the floor, for example, and is followed by the vehicle. The guide-path may be made from wire, paint, or tape, or some combination thereof. In any case, the guide-path must be purposefully installed and maintained, and if changes are to be made to the vehicles translation through the environment, then the guide-path must be manually (i.e., physically) modified. Breaks in the guide-path can lead to system malfunction or stoppage.
Other systems use laser techniques that employ fixed targets in the facility and provide position data to the vehicle for use in geometric calculations used in navigation. Such systems require known positioning of the targets and mapping of the facility with respect to the targets. The use of lasers requires careful selection of the target locations, and the need to maintain “line of sight” relationships to the vehicles. Therefore, the usefulness of such a system is highly dependent an the stability and maintenance of the targets and the required line of sight relationships. Blocking a line of sight path between a target and the vehicle's laser or a corresponding receiver can cause system malfunction or stoppage.
Free ranging systems use odometry or inertial measurement units, or both and provide navigation based on a priori knowledge of the facility layout. To navigate, the system must know where within the facility it is, as a reference, and then tracks its way through according to the facility layout and its translation measurements with respect thereto. Such systems typically determine their location by measuring translation relative to at least one known position or reference point and navigates according to those measurements. These systems are extremely susceptible to error build-up over time, which limits their accuracy. Like the other systems, these types of systems are unable to respond to changes in the workplace.
“Evidence grids” have been suggested in some literature as a way to more effectively represent an area or volume. An evidence grid may take the form of a 2-D or 3-D pre-defined pattern of “voxels” representing the area or volume. Each “voxel” represents a point in space and may contain occupancy information about the point. Due to the sparsity of the data in 2-D evidence grids, they tend to be unreliable and impractical in real-world environments. Three-dimensional evidence grids, as known in the prior art, are more promising due to the much richer data set they tend to include. However, construction of such 3-D evidence grids has been computationally burdensome—to the point of having limited real-world application.
To alleviate such problems, most systems and methods rely primarily on “feature extraction” to reduce the typically computational burdens—by making relatively informed guesses from the voxel data collected within the environment based on patterns of voxel information presumed to represent one or more features of known objects. This can lead to unsatisfactory and potentially intolerable results when guesses are wrong or when the computational burden makes the system too slow for practical applications.